FIG. 1 shows a simplified architecture of a communications switch 10 or a router. Packets 12 of traffic arrive at ingress queues and are switched by a switching fabric to egress queues before departing from an output port 14 of the switch. When the depth of packets in any queue exceeds a discard threshold (Dt) 16, packets arriving at that queue may be dropped in accordance with a tail drop procedure. That is, packets at the end of the queue are dropped until the queue depth (also called the queue occupancy) recedes below the discard threshold. A problem with this procedure, in the case of TCP connections, is that packets can be dropped from a single TCP connection because of the nature of the protocol.
Another type of discard procedure, which alleviates the aforementioned problem with TCP connections, is random early packet discard (RED for short). RED uses the queue depth (queue occupancy) to determine whether to keep or discard each packet as it arrives at the queue. This is done by determining a discard probability, which is dependent on the average depth of the queue (also called average queue depth or average queue occupancy), and comparing the discard probability to a random number. If the discard probability is greater than the random number the packet is discarded.
FIG. 2 shows a graph of an example discard probability function versus average queue depth. According to this function, the discard probability is zero until a minimum-threshold is reached, thereafter the discard probability increases linearly until a maximum threshold is reached. For average queue depths greater than the maximum threshold the discard probability is 100%.
FIG. 3 shows graphs of discard probability functions for a variation of RED, known as, weighted RED. In this case, there are three discard probability functions (green, yellow, and red) and each will result in a different discard probability for the same average queue depth. The particular discard probability function that is used for a packet depends on the drop precedence (colour) of the packet. The drop precedence (DP) is determined by examining the DiffServ Code Point (DSCP) field in the IP header of the packet. Packets that exceed agreements on their connections have their drop precedence (colour) changed by an IP policing procedure. As with the RED procedure, in weighted RED the determination to keep or discard a packet is made by comparing the discard probability of the packet to a random number, discarding the packet when the probability exceeds the number. Variations of this procedure include having more discard probability functions, and having different probability curves in accordance with a class of service (CoS) to which the packet belongs. The CoS of a packet is also determined by examining the DSCP field in the IP header.
FIG. 4 shows another example of weighted RED with the discard probability functions having shapes that are generally accepted to work well. The figure includes three graphs for three colours. For each colour, its function provides the discard probability that increases linearly from 0% to MAXp, as the average queue depth increases from its minimum threshold (MINth) to its maximum threshold (MAXth). Above MAXth, the discard probability is 100%. Different vendors and different drop precedence (colour) functions will have different values for MAXp, MINth, and MAXth shown in the figure. In the figure, MAXp, which is less than 100%, is same for all the colours. Discard probability functions having different shapes and curves are possible.
It is therefore summarized that whether a packet arriving to the RED system is queued or dropped depends on the current discard probability and the colour (relative priority) of the packet. Discard probability, in turn, depends on the average queue depth. These relations can be formalized as follows.New Navg=Previous Navg+W×(Ncur−Previous Navg)  (1)P(colour)=Fcolour(New Navg)  (2)Navg is the average queue depth, and 0<W<1 is a moving average weight that determines how closely the average follows the actual (current) queue depth, Ncur. If W is small, the average will lag behind the actual queue depth; conversely, the average will follow closely the actual queue depth when W is large. P is a discard probability, different for every colour of a packet (colour∈{red, yellow, green}), and F(Navg) is a linear discard probability function that returns values that depend on the colour and the average queue depth. FIGS. 2-4 give some example functions.
As previously mentioned, the determination of whether to discard or keep a packet is made by comparing the discard probability of the packet to a random number (RN). There are two common methods for selecting and comparing a random number, or random variable, to the discard probability. These methods are the geometric random variable (GRV) method and the uniform random variable (URV) method.
FIGS. 5 and 6 show a comparison of the results of the GRV and URV methods with a constant average queue depth. FIG. 5 is the GRV method and FIG. 6 is the URV method. In the figures the horizontal lines depict time and the small vertical lines depict packet discards. According to the geometric random variable (GRV) method, a new random number is selected for each packet arriving at a queue. If the discard probability for the packet exceeds the random number then the packet is discarded. As FIG. 5 shows, the resulting discards are randomly distributed in time. The URV method, on the other hand, selects a new random number only after a packet has been discarded. The URV method, therefore, counts the number of packets (count) since the last discard and multiplies the count by the discard probability. If the resulting product is greater than the random number then the packet is discarded, the count set to zero, and a new random number is generated. Otherwise the packet is accepted and the count is incremented.
URV Algorithm:
Initialize packet count=0;IF (packet count*P(colour))>RN), THEN{discard the packet;get a new RN;packet count=0;}Else{accept the packet;increment packet count (i.e., packet count=packet count+1)}
It has been shown that URV method gives a better performance than GRV method because it usually achieves a more uniform distribution of packet discards over time, as seen in FIG. 6. This is desirable because if too many packets are discarded consecutively and/or intervals between accepted packets are long, a global synchronization with several connections may occur, resulting in reduction of their windows at the same time.
Although the URV method provides the desirable result of uniformly distributing packet discards in time, it requires an additional multiply operation over the GRV method. This extra multiplication takes a significant amount of processing time. As an example, assume that a typical network processor has 56 cycles to process a 40-byte packet at 9.14 Gb/s (equivalent to OC-192) rate. Each multiplication operation takes 6 cycles to complete. This yields a total of 12 cycles for the multiplication part of the discard calculations. A problem with this approach is that, in the case of packets arriving at OC-192 rate, the URV discard procedure leaves only 44 cycles for the remainder of the discard processing, such as threshold checking. At these rates, every cycle is precious and saving them is important. The present invention provides novel ways to perform RED more efficiently, requiring less processing power and/or time, making it more suitable for high-speed applications.
Furthermore, to perform the RED algorithm, discard probability, P(colour), which depends on average queue depth, Navg, must be calculated by using formulae (1) and (2). There are several ways of calculating formulae (1) and (2). Two common variations are described here, i.e., “background method” and “arrival method”. In the first method, a background process is invoked every T seconds. This process calculates average queue depth and discard probability using formulae (1) and (2) respectively. The obtained values are then used to determine a fate of every packet that arrives to the system during the next T seconds. After that time, the background process is called again, the current queue depth is fetched, and new average queue depth and discard probability are computed. In the second method, on the other hand, average queue depth and discard probability are not calculated periodically but every time a packet arrives to the system. Again, formulae (1) and (2) above are used for the calculations and the packet is either accepted or discarded based on the calculated value of discard probability. Whichever method is used, either URV or GRV procedure described above can be employed to perform accept/discard action.
When using “the arrival method”, however, there may be an additional problem in calculating average queue depth after idle times, i.e., when the queue is empty. Referring to FIG. 7, which is a graph of actual (instantaneous) queue depth 70 compared to average queue depth 72. According to the procedure for calculating average queue depth when the queue is empty, the calculated average queue depth can incorrectly remain constant as shown by solid line 74 when in fact the correct average queue depth shown by dotted line 76 is decreasing.
This is explained as follows:
In known procedures of RED, when the queue goes empty, a timestamp is taken. When the next packet arrives, calculation of the average queue depth is made. When the queue is empty, formula (3) below, instead of formula (1) mentioned above, is used to calculate the average queue depth;New Navg=Previous Navg×function(idle time, W)  (3)The idle time is found by subtracting the current time from the queue empty timestamp. If the idle time is very small, the “function” given in formula (3) will be essentially equal to 1. If this occurs, the Navg does not change. Then the packet is transmitted, the queue goes empty, and a short time later another packet arrives. Again idle time is very small and Navg does not change. This can continue indefinitely. This error in the determination of the average queue depth, which could lead to needless discard of packets, is undesirable.
It is therefore apparent that improved techniques of discarding packets are desired. The techniques should require less processing power and/or time.
A further improvement in accuracy of calculating the average queue depth is also required for better performance of the random early packet discard operation.